package argo.hot100.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class CanFinish {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> edges = new ArrayList<>();
        int[] inegs = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }

        for (int[] prerequisite : prerequisites) {
            edges.get(prerequisite[1]).add(prerequisite[0]);
            inegs[prerequisite[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < inegs.length; i++) {
            if (inegs[i] == 0) {
                queue.offer(i);
            }
        }

        int selected = 0;

        while (!queue.isEmpty()) {
            Integer course = queue.poll();
            selected++;
            for (Integer toCourse : edges.get(course)) {
                inegs[toCourse]--;
                if (inegs[toCourse] == 0) {
                    queue.offer(toCourse);
                }
            }
        }

        return selected == numCourses;

    }
}
